翻訳と辞書 Words near each other ・ Polyortha euchlorana ・ Polyortha evestigana ・ Polyortha glaucotes ・ Polynomial and rational function modeling ・ Polynomial arithmetic ・ Polynomial basis ・ Polynomial chaos ・ Polynomial code ・ Polynomial conjoint measurement ・ Polynomial decomposition ・ Polynomial delay ・ Polynomial Diophantine equation ・ Polynomial expansion ・ Polynomial function theorems for zeros ・ Polynomial greatest common divisor ・ Polynomial hierarchy ・ Polynomial identity ring ・ Polynomial interpolation ・ Polynomial kernel ・ Polynomial least squares ・ Polynomial lemniscate ・ Polynomial long division ・ Polynomial matrix ・ Polynomial regression ・ Polynomial remainder theorem ・ Polynomial representations of cyclic redundancy checks ・ Polynomial ring ・ Polynomial sequence ・ Polynomial signal processing ・ Polynomial SOS Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Polynomial hierarchy ： ウィキペディア英語版 Polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. ==Definitions== There are multiple equivalent definitions of the classes of the polynomial hierarchy. :$\backslash Sigma\_^\; :=\; \backslash mbox^^\; :=\; \backslash mbox^\; =\; ,\; \backslash Pi\_1^\; =$, and $\backslash Delta\_2^\; =$ *), let $p$ be a polynomial, and define : $\backslash exists^p\; L\; :=\; \backslash left\backslash ^\; \backslash right)\; \backslash langle\; x,w\; \backslash rangle\; \backslash in\; L\; \backslash right.\; \backslash right\backslash \},$ where $\backslash langle\; x,w\; \backslash rangle\; \backslash in\; \backslash ^$ * is some standard encoding of the pair of binary strings ''x'' and ''w'' as a single binary string. ''L'' represents a set of ordered pairs of strings, where the first string ''x'' is a member of $\backslash exists^p\; L$, and the second string ''w'' is a "short" ($|w|\; \backslash leq\; p(|x|)$) witness testifying that ''x'' is a member of $\backslash exists^p\; L$. In other words, $x\; \backslash in\; \backslash exists^p\; L$ if and only if there exists a short witness ''w'' such that $\backslash langle\; x,w\; \backslash rangle\; \backslash in\; L$. Similarly, define : $\backslash forall^p\; L\; :=\; \backslash left\backslash ^\; \backslash right)\; \backslash langle\; x,w\; \backslash rangle\; \backslash in\; L\; \backslash right.\; \backslash right\backslash \}$ Note that De Morgan's Laws hold: $\backslash left(\; \backslash exists^p\; L\; \backslash right)^\; =\; \backslash forall^p\; L^$ and $\backslash left(\; \backslash forall^p\; L\; \backslash right)^\; =\; \backslash exists^p\; L^$, where ''L''c is the complement of ''L''. Let $\backslash mathcal$ be a class of languages. Extend these operators to work on whole classes of languages by the definition :$\backslash exists^\; \backslash mathcal\; :=\; \backslash left\backslash \; \backslash right\backslash \}$ :$\backslash forall^\; \backslash mathcal\; :=\; \backslash left\backslash \; \backslash right\backslash \}$ Again, De Morgan's Laws hold: $\backslash exists^\; \backslash mathcal\; =\; \backslash forall^\; \backslash mathcal$ and $\backslash forall^\; \backslash mathcal\; =\; \backslash exists^\; \backslash mathcal$, where $\backslash mathcal\; =\; \backslash left\backslash$. The classes NP and co-NP can be defined as $=\; \backslash exists^$, and $=\; \backslash forall^$, where P is the class of all feasibly (polynomial-time) decidable languages. The polynomial hierarchy can be defined recursively as :$\backslash Sigma\_0^\; :=\; \backslash Pi\_0^\; :=$ :$\backslash Sigma\_^\; :=\; \backslash exists^\; \backslash Pi\_k^$ :$\backslash Pi\_^\; :=\; \backslash forall^\; \backslash Sigma\_k^$ Note that $=\; \backslash Sigma\_1^$, and $=\; \backslash Pi\_1^$. This definition reflects the close connection between the polynomial hierarchy and the arithmetical hierarchy, where R and RE play roles analogous to P and NP, respectively. The analytic hierarchy is also defined in a similar way to give a hierarchy of subsets of the real numbers. |3=An equivalent definition in terms of alternating Turing machines defines $\backslash Sigma\_k^$ (respectively, $\backslash Pi\_k^$) as the set of decision problems solvable in polynomial time on an alternating Turing machine with $k$ alternations starting in an existential (respectively, universal) state. }} 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polynomial hierarchy」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.